#include<vector>  
#include<iostream> 
 
  
using namespace std;  
  
class Solution
{
public:
    int lengthOfLIS(vector<int> &nums)
    {
        int n = nums.size();
        if (n == 0)
            return 0;

        vector<int> dp(n, 1); // dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
        int maxLength = 1;    // 最长递增子序列的长度

        for (int i = 1; i < n; ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                if (nums[j] < nums[i])
                {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            maxLength = max(maxLength, dp[i]);
        }

        return maxLength;
    }
};
#ifndef COMPILER_ONLINE  
#include "header.cpp"  
#endif  
  
void Test1() {  
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};  
    Solution solution;  
    int result = solution.lengthOfLIS(nums);  
    if (result == 4) {  
        cout << "通过了用例1, 测试[10,9,2,5,3,7,101,18]通过....OK!" << endl;  
    } else {  
        cout << "没有通过用例1, 测试[10,9,2,5,3,7,101,18]失败....ERROR!" << endl;  
    }  
}  
  
void Test2() {  
    vector<int> nums = {0, 1, 0, 3, 2, 3};  
    Solution solution;  
    int result = solution.lengthOfLIS(nums);  
    if (result == 4) {  
        cout << "通过了用例2, 测试[0,1,0,3,2,3]通过....OK!" << endl;  
    } else {  
        cout << "没有通过用例2, 测试[0,1,0,3,2,3]失败....ERROR!" << endl;  
    }  
}  
  
void Test3() {  
    vector<int> nums = {7, 7, 7, 7, 7, 7};  
    Solution solution;  
    int result = solution.lengthOfLIS(nums);  
    if (result == 1) {  
        cout << "通过了用例3, 测试[7,7,7,7,7,7]通过....OK!" << endl;  
    } else {  
        cout << "没有通过用例3, 测试[7,7,7,7,7,7]失败....ERROR!" << endl;  
    }  
}  
  
void Test4() {  
    vector<int> nums = {1};  
    Solution solution;  
    int result = solution.lengthOfLIS(nums);  
    if (result == 1) {  
        cout << "通过了用例4, 测试[1]通过....OK!" << endl;  
    } else {  
        cout << "没有通过用例4, 测试[1]失败....ERROR!" << endl;  
    }  
}  
  
void Test5() {  
    vector<int> nums = {1, 3, 6, 7, 9, 4, 10, 5, 6};  
    Solution solution;  
    int result = solution.lengthOfLIS(nums);  
    if (result == 6) {  
        cout << "通过了用例5, 测试[1,3,6,7,9,4,10,5,6]通过....OK!" << endl;  
    } else {  
        cout << "没有通过用例5, 测试[1,3,6,7,9,4,10,5,6]失败....ERROR!" << endl;  
    }  
}  
  
void Test6() {  
    vector<int> nums = {2, 2};  
    Solution solution;  
    int result = solution.lengthOfLIS(nums);  
    if (result == 1) {  
        cout << "通过了用例6, 测试[2,2]通过....OK!" << endl;  
    } else {  
        cout << "没有通过用例6, 测试[2,2]失败....ERROR!" << endl;  
    }  
}  
  
void Test7() {  
    vector<int> nums = {10, 9, 2, 5, 3, 4};  
    Solution solution;  
    int result = solution.lengthOfLIS(nums);  
    if (result == 3) {  
        cout << "通过了用例7, 测试[10,9,2,5,3,4]通过....OK!" << endl;  
    } else {  
        cout << "没有通过用例7, 测试[10,9,2,5,3,4]失败....ERROR!" << endl;  
    }  
}  
  
int main() {  
    Test1();  
    Test2();  
    Test3();  
    Test4();  
    Test5();  
    Test6();  
    Test7();  
    return 0;  
}